package com.cn.codebrush.数组.双指针;

/**
 * @Author Boolean
 * @Date 2022/6/16 15:30
 * @Version 1.0
 */
public class No11盛最多水的容器 {
    public static void main(String[] args) {

    }


    /**
     * 双指针  双重循环可以优化成双指针
     * @param height
     * @return
     */
    public int maxArea3(int[] height) {
        int n = height.length;
        int left=0,right=n-1;
        int len = right-left;
        int h = Math.min(height[left],height[right]);
        int res = h*len;
        while(left<right){
            if(height[left] >= height[right]){
                right--;
            }else {
                left++;
            }
            h = Math.min(height[left],height[right]);
            len = right-left;
            res = Math.max(res,(h*len));
        }

        return res;
    }



    /**
     * 动态规划 优化    超出时间限制
     * 55 / 60 个通过测试用例
     * @param height
     * @return
     */
    public int maxArea2(int[] height) {
        int n = height.length;
        int res = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int h = Math.min(height[i],height[j]);
                res = Math.max(res,(h * (j-i)));
            }
        }
        return res;
    }

    /**
     * 动态规划
     * 52 / 60 个通过测试用例    超出内存限制
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int n = height.length;
        int[][] dp = new int[n][n];
        dp[0][0] = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int h = Math.min(height[i],height[j]);
                dp[i][j] = h * (j-i);
            }
        }

        int res = dp[0][0];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                res = Math.max(res,dp[i][j]);
            }
        }

        return res;
    }
}
